package com.example.leetdemo.finash;

public class Solution6203 {
    public int numberOfPaths(int[][] grid, int k) {
        int[][][] dp = new int[grid.length + 1][grid[0].length + 1][k];
        dp[0][0][0] = 1;
        dp[0][1][0] = 1;
        dp[1][0][0] = 1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                int t = grid[i][j] % k;
                if (i == j && i == 0) {
                    dp[i + 1][j + 1][t] = 1;
                    continue;
                }
                for (int l = 0; l < k; l ++) {
                    int y = (l - t + k) % k;
                    dp[i + 1][j + 1][l] = (dp[i + 1][j][y] + dp[i][j + 1][y])% 1000000007 ;
                }
            }
        }
        return dp[grid.length][grid[0].length][0];
    }
}
